An aspect of the invention relates, in general, to computer programs, and in particular, to branch instructions used within computer programs.
A computer program (a.k.a., program or application) is a sequence of instructions written to perform a specific task within a computing environment. Each instruction performs a particular operation, such as add, subtract, move, shift, compare, store, and load, to name just a few examples. The instructions are fetched by a processor in sequential order, unless a particular instruction directs the processing to continue at a different location. For instance, instead of fetching the next sequential instruction, a branch instruction may direct the processor to fetch an instruction at a different location in the program. On average, a program has a branch every four to five instructions.
In some computer micro-architectures, an instruction is executed to completion before the next instruction begins. However, in other micro-architectures, pipelining is used to increase the number of instructions that can be concurrently executed. In pipelining, the processing of an instruction is split into a plurality of independent steps, such as fetch, decode, dispatch, issue, execute and complete, as well as potentially others, which are executed in a pipeline. As the first step of the instruction (e.g., fetch) completes in the pipeline, then another instruction may begin, and so forth.
Pipelining also facilitates the execution of instructions out-of-order from their position in the program. For instance, the issue step has associated therewith an issue queue, which receives instructions in-order of the program. The issue queue is responsible for holding each instruction until the data (e.g., operands) needed by the instruction is available, and then it issues the instruction for execution. If the data for one instruction is available prior to the data for another instruction, then the one instruction can be sent out for execution before the other instruction (out-of-order processing), even if the other instruction is first in the program. For example, if instructions A, B and C are to be executed, where A is the oldest and C is the youngest, if B is dependent on A, and C is not dependent on A or B, then the instructions can be issued in the order of A, C, B, thereby utilizing the pipeline at a higher rate and allowing instructions to be processed faster.
The out-of-order processing, however, is constrained by an out-of-order window/queue of a finite size in which instructions may be processed out-of-order. The issue window is typically 100 or less instructions and the reorder window, which re-orders the instructions back into its original order, is typically 200 or less instructions, where the 100 is a subset of the 200.